#include "../tools.h"

class Cmp{
public:
    bool operator()(const pair<int,int>& a, const pair<int,int>&b) const{
        return a.second > b.second;
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        if(nums.size() == 0 || k == 0) return {};

        unordered_map<int, int> dict;
        for(auto& e: nums){
            if(dict.find(e) == dict.end()) dict[e] = 1;
            else dict[e]++;
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, Cmp> qMin;
        for(auto& e: dict){
            if(qMin.size() < k) qMin.push(e);
            else {
                auto top_e = qMin.top();
                if(top_e.second > e.second) continue;
                qMin.pop();
                qMin.push(e);
            }
        }
        
        vector<int> res;
        while(!qMin.empty()){
            auto e = qMin.top();
            qMin.pop();
            res.push_back(e.first);
        }
        return res;
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    vector<int> nums = {1,1,1,2,2,3};
    int k = 2;

    vector<int> res = sol.topKFrequent(nums, k);
    for(auto& e: res)
        cout << e << " ";
    


    return 0;
}
